package com.nlp.trie.bigramSeg;
/**
 * 二元分词
 * @author ygsong.abcft
 *http://thulac.thunlp.org/
 */

import java.util.ArrayDeque;

public class Segmenter {
	
	TernarySearchTrie dict = TernarySearchTrie.getInstance();//词典
	final double minValue = Double.NEGATIVE_INFINITY;
	
	CnToken startNode;//开始词
	public CnToken endNode;//结束词
	public ArrayDeque<CnToken> split(String sentence){
		AdjList segGraph = getSegGraph(sentence);//得到切分词图
		//从前往后遍历切分词图中的每个词
		for (CnToken currentWord : segGraph) {
			//得到当前的前驱词
			CnTokenLinkedList prevWordList = segGraph.prevWordList(currentWord.start);
			double wordProb = minValue;//候选词概率
			CnToken minToken = null;
			if (prevWordList == null) {
				continue;
			}
			for (CnToken preWord : prevWordList) {
				double currentProb = transProb(preWord, currentWord)
						+preWord.nodeProb;
				if (currentProb > wordProb) {
					wordProb = currentProb;
					minToken = preWord;
				}
			}
			currentWord.bestPrev = minToken;//设置氮气词的最佳前驱词
			currentWord.nodeProb = wordProb;//设置当前词的词概率
		}
		return bestPath();
	}
	/**
	 * 根据最佳前驱节点找切分路径
	 * @return
	 */
	private ArrayDeque<CnToken> bestPath() {
		//切分出来的词序列
		ArrayDeque<CnToken> seq = new ArrayDeque<CnToken>();
		//从右向左找最佳前驱节点
		for(CnToken t = endNode.bestPrev; t != startNode; t= t.bestPrev) {
			seq.addFirst(t);
		}
		return seq;
	}
	//前后两个词的转移概率
	private double transProb(CnToken preWord, CnToken currentWord) {
		return preWord.logProb;
	}
	/**
	 * 返回切分词图
	 * @param sentence
	 * @return
	 */
	public AdjList getSegGraph(String sentence) {
		int sLen = sentence.length();//字符串长度
		AdjList g = new AdjList(sLen + 2);//存储所有被切分的可能的词
		startNode = new CnToken(-1, 0, 0,"start");
		g.addEdge(startNode);
		endNode = new CnToken(sLen, sLen+1, 0, "end");//句子结束词的位置是句子长度加一
		System.out.println(endNode);
		g.addEdge(endNode);
		int j;//词的结束位置
		TernarySearchTrie.PrefixRet wordMatch = new TernarySearchTrie.PrefixRet();
		for(int i =0; i < sLen;) {
			boolean match = dict.getMatch(sentence, i, wordMatch);//到词典中查询
			if (match) {//已经匹配上
				for (WordEntry word : wordMatch.values) {
					j = i + word.word.length();
					double logProb = Math.log(word.freq)-Math.log(dict.n);
					g.addEdge(new CnToken(i, j, logProb, word.word));
				}
				i = wordMatch.end;
			}else {
				j = i +1;
				double logProb = Math.log(1) - Math.log(dict.n);
				g.addEdge(new CnToken(i, j, logProb, sentence.substring(i, j)));
				i = j;
			}
		}
		return g;
	}

}
